package com.problem;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yyh
 * @Date: 2019/12/20 16:39
 */
public class SudokuSolver {

    private static List<Node> nodes = new ArrayList<>();
//    private static int count = 0;
//    private static int check = 0;


    static boolean[][] rb = new boolean[9][10];
    static boolean[][] cb = new boolean[9][10];
    static boolean[][] c1b = new boolean[9][10];

    private void init(String[][] board1) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (!".".equals(board1[i][j])) {
                    setBoolean(i, j, Integer.valueOf(board1[i][j]), true);
                }
            }
        }
    }

    private void setBoolean(int i, int j, int v, boolean b) {
        rb[i][v] = b;
        cb[j][v] = b;

        int a = i / 3 == 0 ? j / 3 :
                i / 3 == 1 ? 3 + j / 3 :
                        2 * 3 + j / 3;
        c1b[a][v] = b;
    }

    /**
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     * 空白格用 '.' 表示。
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {
        //按顺序 行-》列-》方格 检查

        String[][] board1 = c2s(board);
        init(board1);
        int r = 0;
        int c = 0;
        int i = 1;
        xxx(r, c, i, board1, nodes);
        s2c(board1, board);
        printC(board);
    }

    private void xxx(int r, int c, int i, String[][] board1, List<Node> nodes) {
        retry:
        for (; r < 9; r++) {
            for (; c < 9; c++) {
                if (!".".equals(board1[r][c])) {
                    continue;
                }
                for (; i < 10; i++) {
                    //count++;
                    String x = "" + i;
                    //if (check(board1, r, c, x)) {
                    if (newCheck(r, c, x)) {
                        board1[r][c] = x;
                        nodes.add(new Node(r, c, x));
                        setBoolean(r, c, Integer.valueOf(x), true);
                        i = 1;
                        break;
                    }
                    if (i == 9) {
                        //当前格子没有合适的数字，上一个格子重新填
                        if (nodes.size() > 0) {
                            Node node = getPrevNode(board1);
                            r = node.getR();
                            //todo 不知道为啥循环的时候会自增，可能是retry的原因？
                            r--;
                            c = node.getC();
                            i = node.getNextV();
                            continue retry;
                        }
                    }
                }
                //printS(board1);
            }
            c = 0;
        }
    }


    private boolean newCheck(int row, int column, String x) {
        return !(rb[row][Integer.valueOf(x)] || cb[column][Integer.valueOf(x)] || c1b[row / 3 == 0 ? column / 3 :
                row / 3 == 1 ? 3 + column / 3 :
                        2 * 3 + column / 3][Integer.valueOf(x)]);
    }

    /**
     * 从尾部开始，将数字不合理的位置重置为'.'
     * 同时返回可以重新填写的位置
     *
     * @return
     */
    public Node getPrevNode(String board1[][]) {
        Node node = nodes.remove(nodes.size() - 1);
        int cr = node.getR();
        int cc = node.getC();
        board1[cr][cc] = ".";

        setBoolean(cr, cc, Integer.valueOf(node.getV()), false);
        if (node.getNextV() == -1) {
            return getPrevNode(board1);
        }
        return node;
    }

    private class Node {
        //位置信息 行、列
        int r, c;
        //值
        String v;

        protected Node(int r, int c, String v) {
            this.r = r;
            this.c = c;
            this.v = v;
        }

        public int getR() {
            return r;
        }

        public int getC() {
            return c;
        }

        public String getV() {
            return v;
        }

        public int getNextV() {
            if ("9".equals(v)) {
                return -1;
            }
            return Integer.valueOf(v) + 1;
        }
    }


    private void s2c(String[][] array, char[][] c) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                c[i][j] = array[i][j].charAt(0);
            }
        }
    }

    private String[][] c2s(char[][] array) {
        String[][] s = new String[array.length][];
        for (int i = 0; i < array.length; i++) {
            String[] si = new String[array[i].length];
            for (int j = 0; j < array[i].length; j++) {
                si[j] = String.valueOf(array[i][j]);
            }
            s[i] = si;
        }
        return s;
    }




//    private boolean check(String[][] board, int row, int column, String x) {
//        return checkRow(board, row, x) && checkColumn(board, column, x) && checkChequer(board, row, column, x);
//    }
//
//    private boolean checkRow(String[][] board, int row, String x) {
//        for (int i = 0; i < 9; i++) {
//            check++;
//            if (x.equals(board[row][i])) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    private boolean checkColumn(String[][] board, int column, String x) {
//        for (int i = 0; i < 9; i++) {
//            check++;
//            if (x.equals(board[i][column])) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    private boolean checkChequer(String[][] board, int row, int column, String x) {
//        if (row % 3 == 0) {
//            if (column % 3 == 0) {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row + r][column + 1])) {
//                        return false;
//                    } else if (x.equals(board[row + r][column + 2])) {
//                        return false;
//                    }
//                }
//            } else if (column % 3 == 1) {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row + r][column - 1])) {
//                        return false;
//                    } else if (x.equals(board[row + r][column + 1])) {
//                        return false;
//                    }
//                }
//            } else {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row + r][column - 1])) {
//                        return false;
//                    } else if (x.equals(board[row + r][column - 2])) {
//                        return false;
//                    }
//                }
//            }
//        } else if (row % 3 == 1) {
//            if (column % 3 == 0) {
//                check++;
//                if (x.equals(board[row - 1][column + 1])) {
//                    return false;
//                } else if (x.equals(board[row - 1][column + 2])) {
//                    return false;
//                }
//                if (x.equals(board[row + 1][column + 1])) {
//                    return false;
//                } else if (x.equals(board[row + 1][column + 2])) {
//                    return false;
//                }
//            } else if (column % 3 == 1) {
//                check++;
//                if (x.equals(board[row - 1][column - 1])) {
//                    return false;
//                } else if (x.equals(board[row - 1][column + 1])) {
//                    return false;
//                }
//                if (x.equals(board[row + 1][column - 1])) {
//                    return false;
//                } else if (x.equals(board[row + 1][column + 1])) {
//                    return false;
//                }
//            } else {
//                check++;
//                if (x.equals(board[row - 1][column - 1])) {
//                    return false;
//                } else if (x.equals(board[row - 1][column - 2])) {
//                    return false;
//                }
//                if (x.equals(board[row + 1][column - 1])) {
//                    return false;
//                } else if (x.equals(board[row + 1][column - 2])) {
//                    return false;
//                }
//            }
//
//        } else {
//            if (column % 3 == 0) {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row - r][column + 1])) {
//                        return false;
//                    } else if (x.equals(board[row - r][column + 2])) {
//                        return false;
//                    }
//                }
//            } else if (column % 3 == 1) {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row - r][column - 1])) {
//                        return false;
//                    } else if (x.equals(board[row - r][column + 1])) {
//                        return false;
//                    }
//                }
//            } else {
//                for (int r = 1; r < 3; r++) {
//                    check++;
//                    if (x.equals(board[row - r][column - 1])) {
//                        return false;
//                    } else if (x.equals(board[row - r][column - 2])) {
//                        return false;
//                    }
//                }
//            }
//        }
//        return true;
//    }



    private void printS(String[][] b) {
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                System.out.print(b[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("-------------------------");
    }

    private void printC(char[][] b) {
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                System.out.print(b[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("-------------------------");
    }

    public static void main(String[] args) {
        Long a = System.currentTimeMillis();
        char[][] board = new char[9][9];
//        board[0] = new char[]{'5', '3', '.', '.', '7', '.', '.', '.', '.'};
//        board[1] = new char[]{'6', '.', '.', '1', '9', '5', '.', '.', '.'};
//        board[2] = new char[]{'.', '9', '8', '.', '.', '.', '.', '6', '.'};
//        board[3] = new char[]{'8', '.', '.', '.', '6', '.', '.', '.', '3'};
//        board[4] = new char[]{'4', '.', '.', '8', '.', '3', '.', '.', '1'};
//        board[5] = new char[]{'7', '.', '.', '.', '2', '.', '.', '.', '6'};
//        board[6] = new char[]{'.', '6', '.', '.', '.', '.', '2', '8', '.'};
//        board[7] = new char[]{'.', '.', '.', '4', '1', '9', '.', '.', '5'};
//        board[8] = new char[]{'.', '.', '.', '.', '8', '.', '.', '7', '9'};

//        board[0] = new char[]{'.','.','.','.','4','.','.','.','.'};
//        board[1] = new char[]{'7','.','.','.','.','.','.','.','.'};
//        board[2] = new char[]{'.','2','.','.','.','.','.','.','.'};
//        board[3] = new char[]{'.','.','.','.','.','.','.','.','.'};
//        board[4] = new char[]{'.','.','.','.','.','.','.','.','.'};
//        board[5] = new char[]{'.','.','.','.','.','.','.','.','.'};
//        board[6] = new char[]{'.','.','.','.','.','.','.','2','.'};
//        board[7] = new char[]{'.','.','.','.','.','.','.','.','6'};
//        board[8] = new char[]{'.','.','.','.','7','.','.','.','.'};

        board[0] = new char[]{'.','.','9','7','4','8','.','.','.'};
        board[1] = new char[]{'7','.','.','.','.','.','.','.','.'};
        board[2] = new char[]{'.','2','.','1','.','9','.','.','.'};
        board[3] = new char[]{'.','.','7','.','.','.','2','4','.'};
        board[4] = new char[]{'.','6','4','.','1','.','5','9','.'};
        board[5] = new char[]{'.','9','8','.','.','.','3','.','.'};
        board[6] = new char[]{'.','.','.','8','.','3','.','2','.'};
        board[7] = new char[]{'.','.','.','.','.','.','.','.','6'};
        board[8] = new char[]{'.','.','.','2','7','5','9','.','.'};

        SudokuSolver ss = new SudokuSolver();
        ss.solveSudoku(board);
        System.out.println("时间:" + (System.currentTimeMillis() - a));
//        System.out.println("count:" + count);
//        System.out.println("check:" + check);
    }
}
